
\subsection{Model and Definitions}\label{sec:model}
\subsubsection{Distributed Computing Model}
\label{sec:distmodel}
We model the communication network as an undirected, unweighted\footnote{We restrict our attention on unweighted graphs for the upper bound analysis, however, our algorithm can be extended to weighted graphs as well.}, connected $n$-node graph $G = (V, E)$. Every  node has limited initial knowledge. Specifically, assume that each node is associated with a distinct identity number  (e.g., its IP address). 
%Here for simplicity, we assume that the identity numbers are from the set $\{1, 2, . . . , n\}$ . 
At the beginning of the computation, each node $v$ accepts as input its own identity number and the identity numbers of its neighbors in $G$. The node may also accept some additional inputs as specified by the problem at hand. The nodes are allowed to communicate through the edges of the graph $G$. We assume that the communication occurs in  synchronous  {\em rounds}. 
%In particular, all the nodes wake up simultaneously at the beginning of round 1, and from this point on the nodes always know the number of the current round. 
We will use only small-sized messages. In particular, in each round, each node $v$ is allowed to send a message of size $O(\log n)$ through each edge $e = (v, u)$ that is adjacent to $v$.  The message  will arrive to $u$ at the end of the current round. 
%This is a standard model of distributed computation known as the {\em CONGEST model} \cite{peleg} and has been attracting a lot of research attention during last two decades (e.g., see \cite{peleg} and the references therein).
This is a  widely used  standard model known as the {\em CONGEST model} to study distributed algorithms (e.g., see \cite{peleg, PK09}) and captures the bandwidth constraints inherent in real-world computer  networks. 
%Our algorithms can be easily generalized if $B$ bits  are allowed (for any pre-specified parameter $B$) to be sent through each edge in a round. Typically, as assumed here, $B = O(\log n)$, which is number of bits needed to send a node id in a n-node network. 
(We note that if unbounded-size messages were allowed through every edge in each time step, then the problem addressed here can be trivially solved in $O(D)$ time by collecting all the topological information at one node, solving the problem locally, and then broadcasting the
results back to all the nodes \cite{peleg}.) 

There are several measures of efficiency of distributed algorithms, but we will focus on one of them, specifically, {\em the running time}, i.e. the number of {\em rounds} of distributed communication. Note that the computation that is performed by the nodes locally is ``free'', i.e., it does not affect the number of rounds; however, we will only perform polynomial cost computation locally in any node. We note that in the CONGEST model, it is rather trivial to solve a
problem in $O(m)$ rounds, where $m$ is the number of edges in the network, since
the entire topology (all the edges) can be collected at one node and the problem solved locally. The goal is to design faster algorithms.

\subsubsection{Definitions}
\label{sec:def}
We present notations that we use throughout the paper.
Consider a graph $G = (V, E)$ with conductance $\phi$ and let $|V| = n, |E| = m$. Let $p_{\ell}(s, t)$ denote the probability that a  random walk of length $\ell$ starting from $s$ ends in $t$. In fact, $p_{\ell}(s,t)$ is the probability distribution over the nodes after a walk of length $\ell$ starting from $s$. We simply use $p(t)$ instead of $p_{\ell}(s, t)$ when source node and length is clear from the text. Let $S$ be a subset of $V$. We denote a partition or cut by $(S, \bar{S})$ or sometimes by $(S, V\setminus S)$ interchangeably throughout the paper. For a probability distribution $p(i)$ on nodes, let $\rho_p(i) = p(i)/d(i)$. Let $\pi_p$ denote the ordering of nodes in decreasing order of $\rho_p(i)$.

\begin{definition}[{\bf Conductance and Sparsity}]
\label{def:conductance}
The conductance of a cut $(S, \bar{S})$ (also called as sparsity) is $\phi(S) = \frac{|E(S, \bar{S})|}{\min \{\mbox{vol}(S), 2m - \mbox{vol}(S)\}}$ where $\mbox{vol}(S)$ is the sum of the degrees of nodes in $S$. The conductance of the graph $G$ is $\phi(G) = \min_{S \subseteq V} \phi(S)$. We denote it by only $\phi$, if it is clear from the text.  
\end{definition}
%\vspace{-0.05in}
\begin{definition}[{\bf Balance}]
\label{def:balance}
The balance of a cut $(S, \bar{S})$ is defined as $\min \{\frac{|S|}{|V|}, \frac{|\bar{S}|}{|V|} \}$ and is denoted by $b$. 
\end{definition}

\begin{definition}[{\bf Local Cluster}]
\label{def:balance}
A local cluster with respect to a given vertex $v$ is a subset $S \subset V$ containing  $v$ such that the conductance of $(S, \bar{S})$ is within a quadratic factor of the best possible local cluster containing  $v$. %In other words, the internal edge connections in $S$ are significantly higher than the outgoing edges from $S$.      
\end{definition}

